package sort;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {
    public static void main(String[] args) {
//        int[] arry = {8,9,1,7,2,3,5,4,6,0};
        int[] arry = new int[500000];

//
        for (int i = 0; i <50000; i++) {
            arry[i] = (int)(Math.random()*80000);
        }
        System.out.println(Arrays.toString(arry));
//        shellSort(arry);
        shellSort1(arry);

    }

    //交换法
    public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {  //进行分组
            for (int i = gap; i < arr.length; i++) {  //对分的每一组进行排序
                for (int j = i - gap; j >= 0; j -= gap) {  //对分组内里面的元素进行排序
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
//            System.out.println("第" + (++count) + "次排序：" + Arrays.toString(arr));
        }

        System.out.println(Arrays.toString(arr));
    }

    //移位法
    public static void shellSort1(int[] arr){
        for (int gap = arr.length/2; gap >0 ; gap /=2) {
            //从第gap个元素，逐个对其所在的组进行插入排序
            for (int i = gap; i <arr.length ; i++) {
                int j = i;  //待插入的下标
                int temp = arr[j];  //待插入的值
                if(arr[j] < arr[j-gap]){  //有个步长(从后面往前数)

                    while (j-gap>=0 && temp<arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j -=gap;
                    }

                    //当退出这个while后，就找到了插入的位置
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}
